The present invention generally relates to the field of digital image compression, and more particularly to a method and apparatus for digital image compression which operates on dynamical systems, such as cellular automata (CA).
The need often arises to transmit digital image data across a communications network, such as public or private computer networks (e.g., the Internet), the Plain Old Telephone System (POTS); Cellular Wireless Networks; Local Area Networks (LAN); Wide Area Networks (WAN); and Satellite Communications Systems. Many applications also require digital image data to be stored on electronic devices such as magnetic media, optical disks and flash memories. The volume of data required to encode raw image data is large. Consider a 1024xc3x971024 color photograph digitized at the rate of 24 bits per pixel (bpp). Such a digitized image contains 25,165,824 bits of data. To transmit such an image file over 56 kilobits per second (kps) communications channel (e.g., the rate supported by most POTS through modems), will take over 7 minutes.
The best approach for dealing with the bandwidth limitation and also reduce huge storage requirement is to compress the data. One popular technique for compressing image data combines transform approaches (e.g. the Discrete Cosine Transform, DCT) with psycho-visual techniques. The current industry standard is the so-called JPEG (Joint Photographic Expert Group) format, which is based on DCT.
Some recent inventions (e.g., U.S. Pat. No. 5,881,176 to Keith et al) teach the use of the wavelet transform as the tool for image compression. The bit allocation schemes on the wavelet-based compression methods are generally based on the so-called embedded zero-tree concept taught by Shapiro (U.S. Pat. Nos. 5,321,776 and 5,412,741). Other image compression schemes that utilize wavelets as basis functions are described by Ferriere (U.S. Pat. No. 5,880,856), Smart et al. (U.S. Pat. No. 5,845,243), and Dobson et al (U.S. Pat. No. 5,819,215).
In order to achieve a better compression of digital image data, the present invention use a dynamical system, such as cellular automata transforms (CAT). The evolving fields of cellular automata are used to generate xe2x80x9cbuilding blocksxe2x80x9d for image data. The rules governing the evolution of the dynamical system can be adjusted to produce xe2x80x9cbuilding blocksxe2x80x9d that satisfy the requirements of a low-bit rate image compression process.
The concept of cellular automata transform (CAT) was first taught in U.S. Pat. No. 5,677,956 by Lafe for encrypting and decrypting data. The present invention uses more complex dynamical systems, that produce efficient xe2x80x9cbuilding blocksxe2x80x9d for encoding image data. The present invention also uses a psycho-visual method developed specially for the sub-band encoding process arising from the cellular automata transform. A special bit allocation scheme that also facilitates compressed data streaming is provided as an efficient means for encoding the quantized transform coefficients obtained after the cellular automata transform process.
According to the present invention there is provided a method of compressing image data comprising: determining a multi-state dynamical rule set and an associated transform basis function, receiving input image data, and performing a forward transform using the transform basis function to obtain transform coefficients suitable for reconstructing the input image data.
In accordance with another aspect of the present invention, there is provided a method for zooming an image comprising: determining a multi-state dynamical rule set and an associated transform basis function, receiving input image data, performing a sub-band forward transform using the transform basis function to obtain a set of low frequency transform coefficients, and performing an inverse transform using the transform basis function and the set of low frequency transform coefficients, wherein the resulting image data is a zoomed down version of the input image data.
In accordance with still another aspect of the present invention, there is provided a method for zooming an image comprising: determining a multi-state dynamical rule set and an associated transform basis function receiving input image data, performing a sub-band forward transform using the transform basis function to obtain a set of low frequency transform coefficients, performing a forward transform using the transform basis function and the set of low frequency transform coefficients to generate second transform coefficients, wherein the set of low frequency transform coefficients are used as the input image data, and performing an inverse transform using the transform basis function and the second transform coefficients, wherein the resulting image data is a zoomed up version of the input image data.
In accordance with still another aspect of the present invention, there is provided an apparatus for compressing image data comprising: means for determining a multi-state dynamical rule set and an associated transform basis function, means for receiving input image data, and means for performing a forward transform using the transform basis function to obtain transform coefficients suitable for reconstructing the input image data.
In accordance with still another aspect of the present invention, there is provided an apparatus for zooming an image comprising: means for determining a multi-state dynamical rule set and an associated transform basis function, means for receiving input image data means for performing a sub-band forward transform using the transform basis function to obtain a set of low frequency transform coefficients, and means for performing an inverse transform using the transform basis function and the set of low frequency transform coefficients, wherein the resulting image data is a zoomed down version of the input image data.
In accordance with yet another aspect of the present invention, there is provided an apparatus for zooming an image comprising: means for determining a multi-state dynamical rule set and an associated transform basis function, means for receiving input image data means for performing a sub-band forward transform using the transform basis function to obtain a set of low frequency transform coefficients, means for performing a forward transform using the transform basis function and the set of low frequency transform coefficients to generate second transform coefficients, wherein the set of low frequency transform coefficients are used as the input image data, and means for performing an inverse transform using the transform basis function and the second transform coefficients, wherein the resulting image data is a zoomed up version of the input image data.
In accordance with yet another aspect of the present invention, there is provided a method of edge detection comprising: determining a multi-state dynamical rule set and an associated transform basis function, receiving input image data performing a sub-band forward transform using the transform basis function to obtain a set of high frequency transform coefficients, and performing an inverse transform using the transform basis function and the set of high frequency transform coefficients, wherein the resulting image data provides edge detection of the input image data.
In accordance with yet another aspect of the present invention, there is provided an apparatus for edge detection comprising: means for determining a multi-state dynamical rule set and an associated transform basis function, means for receiving input image data means for performing a sub-band forward transform using the transform basis function to obtain a set of high frequency transform coefficients, and means for performing an inverse transform using the transform basis function and the set of high frequency transform coefficients, wherein the resulting image data provides edge detection of the input image data.
An advantage of the present invention is the provision of a method and apparatus for digital image compression which provides improvements in the efficiency of digital media storage.
Another advantage of the present invention is the provision of a method and apparatus for digital image compression which provides faster data transmission through communication channels.
Still other advantages of the invention will become apparent to those skilled in the art upon a reading and understanding of the following detailed description, accompanying drawings and appended claims.